package com.mytest.leetcode;

import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created by shixi  on 2019/6/24
 */
@Slf4j
public class Solution15 {

    public static void main(String[] args) {
        Solution15 solution = new Solution15();
        int[] nums = {1,-1,-1,0};
        log.info("{}", solution.threeSum(nums));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i< nums.length;i++) {
            if (nums[i] >0){
                break;
            }
            // 基数连续相同的两个数
            if (i>0  && nums[i] == nums[i-1]) {
                continue;
            }

            int R = nums.length - 1;
            for (int L=i+1;L<nums.length;L++){
                // 第一指针，连续相同的两个数
                if (L > i + 1 && nums[L] == nums[L - 1]) {
                    continue;
                }
                // 第二指针（最右），递减
                while(nums[i]+nums[L]+nums[R]>0 && R>L){
                    R--;
                }
                if(nums[i]+nums[L]+nums[R]==0 && R>L){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[L]);
                    list.add(nums[R]);
                    result.add(list);
                }
            }

        }
        return result;
    }

    public List<List<Integer>> threeSum1(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();
        for (int i=0;i< nums.length;i++) {
            for (int j=nums.length-1;j>i;j--) {
                int towSum = nums[i] + nums[j];
                int target = 0- towSum;
                List<Integer> tList = Arrays.stream(nums).boxed().collect(Collectors.toList());
                tList.remove(j);
                tList.remove(i);
                if(tList.contains(target)){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(target);
                    Collections.sort(list);
                    if(!result.contains(list)){
                        result.add(list);
                    }
                }
            }
        }
        return result;
    }

}

